package offer.offer03;

import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Queue;

/**
 * todo: 堆值得一学。
 * 解析中有自定义快排方法, 感觉挺好, 就选一个数, 快排左右扫一遍, 递归左右结果。实现起来比较复杂。
 */
public class S40最小的k个数 {
    /**
     * 71, 直接sort也不差, 感觉如果一个算法复杂度在 nlogn, 那么其实都可以通过LeetCode的提交
     * 维护一个什么东西来存储最小的k个数, 不知道用什么比较合适, TreeMap?
     * 一个自定义comparator的有序的集合?
     * 或者有点像堆?
     */
    public int[] getLeastNumbers(int[] arr, int k) {
        Arrays.sort(arr);
        return Arrays.copyOfRange(arr, 0, k); // 这个虽然是调用system.arrayCopy, 但是和for一样
    }
    /**
     * 19, 不知道性能损失在何处。
     * 做一个大根堆, 然后塞一个poll一个
     */
    public int[] getLeastNumbers2(int[] arr, int k) {
        Queue<Integer> queue = new PriorityQueue<>((a, b) -> b - a);
        for(int i : arr){
            queue.add(i);
            if(queue.size() == k + 1) queue.poll();
        }
        int[] res = new int[k];
        // error: local variables referenced from a lambda expression must be final or effectively final
        // 注意这里有一个forEach的错误, forEach里面不能涉及到外面的变量, 有点难用?
        // int count = 0;
        // queue.forEach(a -> res[count++] = a);
        // System.out.println(queue);
        // for(int i = 0; i < queue.size(); i++){
        //     res[i] = queue.poll();
        // }
        int count = 0;
        for(int i: queue){
            res[count ++] = i;
        }
        return res;
    }
}
